typedef struct {
    int top;	//栈顶，初始化为-1
    char *buf;	
} stack_t;

void stack_init(stack_t **s, int size) {
    *s = malloc(sizeof(stack_t));
    (*s)->top = -1;
    (*s)->buf = malloc(sizeof(char)*size);
}
int is_empty(stack_t *s) {
    return (s->top == -1);
}
void push(stack_t *s, char ch) {
    s->buf[++s->top] = ch;
}
char pop(stack_t *s) {
    return s->buf[s->top--];
}
char top(stack_t *s) {
    return s->buf[s->top];
}

char * removeDuplicateLetters(char * s){
    int in_stack[256] = {0}; //栈中是否存在字符，用于查重
    int remain[256] = {0};   //ASCII，用于记录后面还有没有该字符，用于处理字典序

    int i, cnt = 0, len = strlen(s);
    stack_t *stack;
    stack_init(&stack, len);
    for (i = 0; i < len; i++) { //统计字符
        remain[s[i]]++;
    }

    for (i = 0; i < len; i++) {
        if (in_stack[s[i]]) {
            remain[s[i]]--; //不压栈，更新后面字符情况
            continue;
        }
        else {  //不在栈中
            // 字典序：尽量将小的字符放在前面
            while (!is_empty(stack) && s[i] < top(stack)) {   //不为空，且小于栈顶（类似单调栈的思想）
                if (remain[top(stack)]) {//后面还有该字符，出栈
                    in_stack[top(stack)] = 0;   
                    pop(stack);
                    cnt--;
                } else {    //后面没有该字符，结束弹栈
                    break;
                }
            }
            //为空 或 大于栈顶 或 后面没有栈顶字符了无法弹出
            push(stack, s[i]);
            in_stack[s[i]] = 1;
            remain[s[i]]--;
            cnt++;
        }
    }

    char *res = malloc(sizeof(char) * (cnt+1));
    res[cnt] = '\0';
    for (i = cnt-1; i >=0; i--) 
        res[i] = pop(stack);
    return res;
}












